#include <string>
#include <vector>

using std::string;
using std::vector;

class C_N_Queens
{
public:
    C_N_Queens(int n) : m_n(n), m_queens(vector<int>(n, -1))
    {
        traceback(0);
    };
    vector<vector<string>> result()
    {
        return m_res;
    }

private:
    void traceback(int n)
    {
        if (n == m_n) {
            draw_board();
        }
        else {
            for (int i = 0; i < m_n; ++i) {
                if (invalid(i, n)) {
                    continue;
                }
                else {
                    m_queens[n] = i;
                    traceback(n + 1);
                    m_queens[n] = -1;
                }
            }
        }
    }

    void draw_board()
    {
        vector<string> res;
        for (int i = 0; i < m_n; i++) {
            string s       = string(m_n, '.');
            s[m_queens[i]] = 'Q';
            res.push_back(s);
        }
        m_res.push_back(res);
    }

    bool invalid(int c, int r)
    {
        for (int row = 0; row < r; ++row) {
            if (c == m_queens[row]) {
                return true;
            }
            if (c - m_queens[row] == r - row) {
                return true;
            }
            if (c - m_queens[row] == row - r) {
                return true;
            }
        }
        return false;
    }

private:
    int                    m_n;
    vector<vector<string>> m_res;
    vector<int>            m_queens;
};

vector<vector<string>> N_Queens(int const n)
{
    return C_N_Queens(n).result();
}
